package demo1;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-08-20
 * Time: 19:37
 */
public class TestDemo {
    //给你两个数组--一个是重量数组w,一个是价值数组v
    //在不超过背包重量的情况下,返回其背包中的最大价值
    //bag为背包的最大容量
    public static int ways1(int[] w,int[] v,int bag){

        //表示0位置以后的可以任意选择,不超过重量bag下返回其背包中的最大价值
        return process(w,v,0,bag);
    }

    //index表示当前所处的位置---index位置后面的值我都可以选择
    //rest是背包中剩下的重量
    public static int process(int[] w,int[] v,int index,int rest){
        //base case
        if(rest<0){
            //如果重量为负值---证明当前价值为无效价值,所以返回-1
            return -1;
        }
        if(index==w.length){
            //如果index等于数组长度,证明没有可以选的,那价值就为0
            return 0;
        }
        //接下来有两种选择,一种是我不选择index位置的值
        int p1 = process(w,v,index+1,rest);
        //一种是我选择index位置的值
        int p2 = 0;
        int next = process(w,v,index+1,rest-w[index]);
        if(next!=-1){
            //如果p2得到的价值是有效的,那么久加上index位置的价值
            p2 = v[index] + next;
        }
        //最终选择两种中最大的值
        return Math.max(p1,p2);
    }

    //接下来改为动态规划
    public static int ways2(int[] w,int[] v,int bag){
        //可变参数为 index(当前所处的位置)  bag(当前所剩下的背包重量)
        int N = w.length;
        int[][] dp = new int[N+1][bag+1];
        //知道最后一行weight.length的背包重量都为0--不用设置--系统指定
        //要从下往上面推

        for(int index = N-1 ;index>=0;--index){
            //列是从左往右
            for(int rest = 0;rest<=bag;++rest){
                int p1 = dp[index+1][rest];
                int next =  rest-w[index] <0 ? -1 :dp[index+1][rest-w[index]];
                int p2 = 0;
                if(next!=-1){
                    p2 = next + v[index];
                }
                dp[index][rest] = Math.max(p1,p2);
            }
        }
        return dp[0][bag];
    }

    //给你一个字符串里面都是数字
    //将其数字转化成字符有几种转化方法
    //比如 : 111 ---> AAA,KA,AK ----最多有3转化方法--返回3
    public static int number(String s){
        if(s.length()<0||s==null){
            return 0;
        }
        //0~i-1位置不用管,你的目的是将i后面的数字转化成字符有多少种转化方法
        //肯定是从0位置开始转化
        return process1(0,s.toCharArray());
    }

    public static int process1(int index,char[] str){
        if(index == str.length){
            //如果index走到末尾位置,也就是越界
            //那么转化次数是空串/前面已经做好的决定
            return 1;
        }
        if(str[index]=='0'){
            //如果当前字符是0,那么如果0单独转化时,那么整个就是无效的转化
            return 0;
        }
        //以下有两种转化方法
        //第一种方法是每个位置的字符单转比如 1-->A
        //这个字符转化完之后,就去下一个位置做决定
        int ways = process1(index+1,str);
        //还有一种方法是,在合法的情况下,两个相邻的位置可以进行转化
        if(index + 1<str.length&&((str[index]-'0')*10 + (str[index+1]-'0'))<27){
            ways+=process1(index+2,str);
        }
        return ways;
    }

    //将刚才的方法改为动态规划
    public static int number1(String s){
        char[] str = s.toCharArray();
        int N = str.length;
        //可变参数就是一个i-->下标
        int[] dp = new int[N+1];
        dp[N] = 1;
        //可变参数为i,i依赖i+1,i+2,依赖后面的,又是一个一维表
        //最终要的是dp[0],所有表是从右往左填,0位置就是answer

        for(int i = N-1;i>=0;i--) {
            if (str[i] != '0') {
                int ways = dp[i + 1];
                if (i + 1 < str.length && ((str[i] - '0') * 10 + (str[i + 1] - '0')) < 27) {
                    ways += dp[i + 2];
                }
                dp[i] = ways;
            }
        }
        return dp[0];

    }


    public static void main(String[] args) {
       int[] weights = {3,2,4,7,3,1,7};
       int[] values = {5,6,3,19,12,4,2};
       int bag = 15;
       System.out.println(ways1(weights, values, bag));
       System.out.println(ways2(weights, values, bag));
       System.out.println(number("7210231231232031203123"));
       System.out.println(number1("7210231231232031203123"));

    }

}
